from typing import Optional

from cn.edu.cdu.argorithme.commons.list_node import ListNode


class linked_list_cycle_ii:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        raise NotImplementedError

class solution1(linked_list_cycle_ii):
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cache = set()
        while head:
            if head in cache:
                 return head
            cache.add(head)
            head = head.next
        return None

class solution2(linked_list_cycle_ii):
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return fast
        return None
